package com.cat.dataStructure03;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution34 {
    List<Integer>[] g;
    int[] val;
    int k, ans;
    long dfs(int x, int f) {
        long sum = val[x];
        for (int y : g[x]) {
            if (y != f) {
                sum += dfs(y, x);
            }
        }
        ans += sum % k == 0 ? 1 : 0;
        return sum;
    }
    public int maxKDivisibleComponents(int n, int[][] edges, int[] values, int k) {
        g = new List[n];
        Arrays.setAll(g, x -> new ArrayList<>());
        for (var e : edges) {
            g[e[0]].add(e[1]);
            g[e[1]].add(e[0]);
        }
        val = values;
        this.k = k;
        dfs(0, -1);
        return ans;
    }
}